/*
 * @lc app=leetcode.cn id=707 lang=java
 *
 * [707] 设计链表
 */



// @lc code=start
class MyLinkedList {
    
    class LinkedNode{
        int val;
        LinkedNode next;
        public LinkedNode(){}
        public LinkedNode(int val){this.val=val;}
    }

    int size;
    LinkedNode head;//虚节点

    public MyLinkedList() {
        size=0;
        head=new LinkedNode(0);

    }
    
    public int get(int index) {
        //非法索引
        if(index<0||index>=size){
            return -1;
        }
        LinkedNode cur=head;
        //算上头节点，则查找的是第index+1个节点
        for(int i=0;i<=index;i++){
            cur=cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);

    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            index=0;
        }
        //找到要插入节点的前驱
        LinkedNode pred=head;
        for(int i=0;i<index;i++){
            pred=pred.next;
        }
        LinkedNode newNode=new LinkedNode(val);
        newNode.next=pred.next;
        pred.next=newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return;
        }
        LinkedNode pred=head;
        for(int i=0;i<index;i++){
            pred=pred.next;
        }
        pred.next=pred.next.next;
        size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
// @lc code=end

